/**
 * @program: LeetCode
 * @description: LeetCode : 279. 完全平方数
 * @author: WXY
 * @create: 2023-01-12 17:42
 * @Version 1.0
 **/
public class Num279_numSquares {

    public static int numSquares(int n) {
        int num = (int) Math.sqrt(n);
        //dp[j] : 表示为 j 的完全平方数最少是多少。
        //dp[j] : 表示为 j 的数可以最少由多少个完成平方数组成
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = 10001;
        }
        dp[0] = 0;
        //方式一：外物品，内背包
//        for (int i = 1; i <= n; i++) {
//            for (int j = i * i; j <= n; j++) {
//                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
//            }
//        }
        //方式二:外背包，内物品
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n] == 10001 ? -1 : dp[n];
    }

    public static int numSquares1(int n) {
        //dp[i] : 表示为 i 的完全平方数最少是多少。
        int[] dp = new int[n + 1];
        dp[0] = 0;
        //没有说明是求排列还是求组合，那么先背包和先物品都是可以的，
        //下面是先背包容量，后物品的方式。
        //dp[0] 设置为0，因为要求最少是多少，所以其他的值不能设置为一个小的数，因此设置为一个较大的数100001,超出了题目给的数据范围了。
        for (int i = 1; i <= n; i++) {
            dp[i] = 100001;
            for (int j = 1; j * j <= i; j++) {
                if (dp[i - j * j] != 100001) {
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
        }
        return dp[n] == 100001 ? -1 : dp[n];
    }

    public static void main(String[] args) {
        int i = numSquares1(12);
        System.out.println(i);
    }

}
